package com.jiajia.study;

import com.jiajia.study.printer.BinaryTreeInfo;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉搜索树
 * @author zjiajia
 * @date 2021/1/17 11:31
 */
public class BinarySearchTree<E> implements BinaryTreeInfo{
    /**
     * 大小
     */
    private int size;
    /**
     * 根节点
     */
    private Node<E> root;
    /**
     * 比较器
     */
    private Comparator<E> comparator;

    public BinarySearchTree(Comparator<E> comparator){
        this.comparator = comparator;
    }

    public BinarySearchTree(){

    }

    /**
     * 大小
     * @return  大小
     */
    public int size(){
        return size;
    }

    /**
     * 是否为空
     * @return  是否为空
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 清空
     */
    public void clear(){
        root = null ;
        size = 0;
    }

    /**
     * 是否包含元素
     * @param element   元素
     * @return          是否包含
     */
    public boolean contains(E element){
        return node(element) != null;
    }

    /**
     * 添加树节点
     * @param element   添加的元素
     */
    public void add(E element){
        elementNotNullCheck(element);
        // 根节点
        if(root == null){
            root = new Node(element,null);
            size ++ ;
            return;
        }
        //
        Node<E> node = root;
        Node<E> parent = root;
        int compare = 0;
        // 找到父节点
        while (node != null){
            compare = compare(element, node.element);
            parent = node;
            if(compare > 0){
                node = node.right;
            }else if (compare < 0){
                node = node.left;
            }else {
                // 相等就直接退出 ,如果引用类型直接覆盖原来的值
                node.element = element;
                return;
            }
        }
        // 添加的节点
        Node<E> newNode = new Node<E>(element,parent);
        // 往左加还是往右加
        if(compare > 0 ){
            parent.right = newNode;
        }else if(compare < 0){
            parent.left = newNode;
        }
        size ++ ;

    }

    /**
     * 删除节点：
     *  1 删除度为0的节点，也就是叶子节点
     *  2 删除度为1的节点
     *  3 如果删除的是度为2的节点，让前驱/后继节点的值覆盖原节点，然后删除前驱/后继节点
     *      ：度为2的节点，前驱/后继节点一定是度为1或者0的节点。那么最后删除一定是度为1或者0的节点
     * @param element   节点元素
     */
    public void remove(E element){
        remove(node(element));
    }

    private void remove(Node<E> node){
        if(node == null){
            return ;
        }
        size--;
        // 度为2的节点
        if(node.hasTowChildren()){
            // 后继节点
            Node<E> successor = successor(node);
            node.element = successor.element;
            // 删除后继节点
            node = successor;
        }
        // 删除node节点 ，度为1或者0
        Node<E> replacement = node.left != null ? node.left : node.right;
        // node 是度为1的节点
        if(replacement != null ){
            replacement.parent = node.parent;
            // 要删除的节点就是根节点
            if(replacement.parent == null ){
                root = replacement;
            }
        }else if(node.parent == null ) { // node是叶子节点，并且是根节点
            root = null;
        }else { // 是叶子节点，并且不是根节点
            if(node == node.parent.left){
                node.parent.left = null;
            }else {
                node.parent.right = null;
            }
        }
    }

    /**
     * 找到元素是element的节点
     * @param element   元素
     * @return          节点
     */
    private Node<E> node(E element){

        Node<E> node = root;
        while (node != null){
            int cmp = compare(element,node.element);
            if(cmp == 0){
                return node;
            }
            if(cmp > 0 ){
                node = node.right;
            }else {
                node = node.left;
            }
        }
        return null;
    }

    /**
     * 元素不能为null检查
     * @param element   元素
     */
    private void elementNotNullCheck(E element){
        if(element == null){
            throw  new IllegalArgumentException("element is not found");
        }
    }

    /**
     * 比较两个节点的大小
     * @param element1  节点1
     * @param element2   节点2
     * @return          如果节点1大于节点2 >0;如果节点1等于节点2 = 0;如果节点1小于节点2<0
     */
    private int compare(E element1 ,E element2){
        if (comparator != null) {
            return comparator.compare(element1, element2);
        }
        return ((Comparable<E>)element1).compareTo(element2);
    }

//    /**
//     * 前序遍历树：
//     *      根节点 左子树 右子树
//     */
//    public void preorderTraversal(){
//        preorderTraversal(root);
//    }
//
//    /**
//     * 前序遍历
//     * @param node  遍历的节点
//     */
//    private void preorderTraversal(Node<E> node){
//        if(node == null ){
//            return;
//        }
//        System.out.println(node.element);
//        preorderTraversal(node.left);
//        preorderTraversal(node.right);
//    }
//
//    /**
//     * 中序遍历：
//     *      左子树 根节点 右子树
//     */
//    public void inorderTraversal(){
//        inorderTraversal(root);
//    }
//
//    /**
//     * 递归中序遍历
//     * @param node  遍历的节点
//     */
//    private void inorderTraversal(Node<E> node){
//        if(node == null){
//            return;
//        }
//        inorderTraversal(node.left);
//        System.out.println(node.element);
//        inorderTraversal(node.right);
//    }
//
//    /**
//     * 后续遍历：
//     *      左子树  右子树   根节点
//     */
//    public void postorderTraversal(){
//
//    }
//
//    /**
//     * 递归后续遍历
//     * @param node  节点
//     */
//    private void postorderTraversal(Node<E> node){
//        if(node == null){
//            return;
//        }
//        inorderTraversal(node.left);
//        inorderTraversal(node.right);
//        System.out.println(node.element);
//
//    }
//
//    /**
//     * 层序遍历：
//     *      思路 ，队列来实现
//     *      首先根节点入队，然后根节点出队，遍历左右子树，左右子树入队
//     *      队列出队，遍历左右子树，左右子树入队
//     *      重复上面的操作。
//     *
//     *      遍历就是每次出队的元素
//     */
//    public void levelOrderTraversal(){
//
//        if(root == null){
//            return;
//        }
//
//        Queue<Node<E>> queue = new LinkedList<>();
//        queue.offer(root);
//
//        while(!queue.isEmpty()){
//            Node<E> node = queue.poll();
//            System.out.println(node.element);
//
//            if(node.left != null){
//                queue.offer(node.left);
//            }
//
//            if(node.right != null){
//                queue.offer(node.right);
//            }
//        }
//
//    }

    /**
     * 前序遍历
     * @param visitor   访问者
     */
    public void preorder(Visitor<E> visitor){
        if(visitor == null){
            return;
        }

    }

    /**
     *
     * @param node      节点
     * @param visitor   访问者，具体的操作逻辑
     */
    private void preorder(Node<E> node ,Visitor<E> visitor){
        if(node== null || visitor.stop){
            return;
        }
        visitor.visit(node.element);

        preorder(node.left,visitor);
        preorder(node.right,visitor);
    }

    /**
     * 中序遍历
     * @param visitor   访问者，操作逻辑封装
     */
    public void inorder(Visitor<E> visitor){
        inorder(root,visitor);
    }
    /**
     *
     * @param node      节点
     * @param visitor   访问者，具体的操作逻辑
     */
    public void inorder(Node<E> node ,Visitor<E> visitor){
        if (node == null || visitor.stop){
            return;
        }
        inorder(node.left,visitor);
        visitor.visit(node.element);
        inorder(node.right,visitor);
    }

    /**
     * 后续遍历
     * @param visitor   访问者
     */
    public void postorder(Visitor<E> visitor){
        postorder(root,visitor);
    }

    /**
     *
     * @param node      节点
     * @param visitor   访问者，具体的操作逻辑
     */
    private void postorder(Node<E> node ,Visitor<E> visitor){
        if(node == null || visitor.stop){
            return;
        }
        postorder(node.left,visitor);
        postorder(node.right,visitor);
        visitor.visit(node.element);
    }

    /**
     * 层级遍历
     * @param visitor   访问者，封装操作逻辑
     */
    public void leverOrder(Visitor<E> visitor){
        if(root == null || visitor.stop ){
            return;
        }

        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            Node<E> node = queue.poll();
            // 访问者的逻辑操作
            visitor.visit(node.element);

            if(node.left != null ){
                queue.offer(node.left);
            }

            if(node.right != null){
                queue.offer(node.right);
            }

        }

    }

    /**
     * 计算二叉树的高度：
     *      计算树的高度，就是计算根节点的高度
     * @return  高度
     */
    public int height(){
        return height(root);
    }

    /**
     * 计算节点的高度:
     *      递归求子节点的高度
     * @param node  节点
     * @return      高度
     */
    public int height(Node<E> node){
        // 如果节点是null  那么就返回0
        if(node == null ){
            return 0;
        }
        // 节点的高度就是等于最大的子节点的高度加1
        return 1 + Math.max(height(node.left),height(node.right));

    }



    /**
     * 通过层序遍历的方式来计算高度
     * @return  高度
     */
    public int heightByLevel(){

        if(root == null) {
            return 0;
        }

        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        // 每一层的节点的个数
        int leverSize = 1;
        // 高度
        int height = 0;
        while(!queue.isEmpty()){

            Node<E> node = queue.poll();
            leverSize --;

            if(node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
            /**
             * 一层遍历完了，高度加1；
             */
            if(leverSize == 0){
                // 上一层出队完成 ，那么剩下的节点个数就是这一层的节点个数，也就是队列的大小
                leverSize = queue.size();
                height ++ ;
            }


        }
        return 0;
    }


    /**
     * 是否是完全二叉树
     * @return 是否
     */
    public boolean isComplete(){
        if(root == null){
            return false;
        }
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()){
            Node<E> node = queue.poll();

            boolean leaf = false;
            if(leaf && !node.isLeaf()){
                return false;
            }

            if(node.left != null){
                queue.poll();
            }else if (node.right != null){
                // 走到这里表示没有左子节点 ，有右子节点
                return false;
            }
            if(node.right != null){
                queue.poll();
            }else {
                // 走到这里表示有左子节点，没有右节点
                // 后面遍历的必须都是叶子节点
                leaf = true;
            }

        }


        return false;
    }

    /**
     * 找到树的前驱节点
     * @return  前驱节点
     */
    public Node<E> predecessor(){
        return predecessor(root);
    }

    /**
     * 找到一个节点的前驱节点
     * @param node  节点
     * @return      前驱节点
     */
    private Node<E> predecessor(Node<E> node){
        // 节点为null  没有前驱节点
        if(node == null) {
            return null;
        }
        // 前驱节点在 ，左 右右右。。。。。
        Node<E> p = node.left;
        if(p != null){
            while(p.right != null){
                p = p.right;
            }
            return p;
        }
        // 前驱节点在  父父父。。。。。
        while (node.parent != null && node.parent.left == node){
            node = node.parent;
        }
        // 走到这里 说明父节点 == null  或者说 父节点的右节点等于节点本身
        return node.parent;
    }

    /**
     * 找到树的后继节点
     * @return  后继节点
     */
    public Node<E> successor(){
        return successor(root);
    }

    /**
     * 找到节点的后继节点
     * @param node  节点
     * @return      后继节点
     */
    private Node<E> successor(Node<E> node){
        if(node == null){
            return null;
        }
        // 后继节点  右左左左。。。。。
        Node<E> p = node.right;
        if(p != null ){
            while ( p.left != null){
                p = p.left;
            }
            return p;
        }

        while(node.parent != null && node.parent.right == node ){
            node = node.parent;
        }

        return  node.parent;

    }






    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        Node<E> myNode = (Node<E>)node;
        return myNode.left;
    }

    @Override
    public Object right(Object node) {
        Node<E> myNode = (Node<E>)node;
        return myNode.right;
    }

    @Override
    public Object string(Object node) {
        Node<E> myNode = (Node<E>)node;
        String parentString = "null";
        if (myNode.parent != null) {
            parentString = myNode.parent.element.toString();
        }
        return myNode.element + "_p(" + parentString + ")";
    }


    /**
     * 树的节点
     * @param <E>   泛型元素
     */
    private static class Node<E>{
        E element;
        /**
         * 左节点
         */
        Node<E> left;
        /**
         * 右节点
         */
        Node<E> right;
        /**
         * 父节点
         */
        Node<E> parent;

        public Node(E element,Node<E> parent){
            this.element = element;
            this.parent = parent;
        }

        /**
         * 是否是叶子节点
         * @return      是否叶子节点
         */
        public boolean isLeaf(){
            return this.left == null && this.right == null;
        }

        /**
         * 是否有两个子节点
         * @return      结果
         */
        public boolean hasTowChildren(){
            return this.left != null && this.right != null;
        }
    }


    /**
     * 遍历树节点的具体逻辑操作
     * @param <E>
     */
    private static abstract class Visitor<E>{

        boolean stop;

        /**
         * 具体操作，提供外面实现
         * @param element   元素
         * @return          操作结果
         */
        public abstract boolean visit(E element);
    }
}
